1. Field of Invention
The present invention relates to a method for simplifying mesh. More particularly, the present invention relates to a fuzzy inference system capable of simplifying meshes in computer graphics by integrating variances of mesh attributes and estimating the cost of removing a portion of data.
2. Description of Related Art
Conventional mesh simplification techniques can be roughly divided into two types, namely, edge collapsing and vertex decimation. FIG. 1 is an illustration showing the working principles behind the conventional edge collapsing method for simplifying mesh. As shown in FIG. 1, vertices(vt, vs) on the left side of the figure is chosen to be the edge collapsing vertices. After collapsing the edge between the vertice(vt, vs), only a single vertex vsxe2x80x2 is left. Hence, one vertex is eliminated and the triangles represented by the vertices(vt, vl, vs) and (vt, vs, vr) are removed. Meanwhile, five edges including vtvs, vtvl, vtvr, vrvs, vsvl originally on the left is reduced to just two edges, namely, vlvsxe2x80x2 and vsxe2x80x2vr.
FIG. 2 is an illustration showing the working principles behind the conventional vertex decimation method for simplifying meshes. In the vertex decimation method, vertices are classified according to the geometry of its neighboring triangles. As shown in FIG. 2, vertices of secondary importance are removed (for example, vm) and the xe2x80x98holexe2x80x99 so created is again triangulated (to form triangles A1, A2 and A3). With such processing, the vertex vm on the left side of the figure is eliminated so that the original five triangles B1, B2, B3, B4, B5 are reduced to just three triangles A1, A2 and A3. Meanwhile, the five edges vmvs, vmvt, vmvu, vmvv, vmvw on the left side of the figure are reduced to just two edges vsvu and vsvv on the right side of the figure.
In the two aforementioned methods, a lower resolution mesh is generated from a high resolution mesh. However, in the process of removing data (collapsing edges or decimating vertices), judging the importance of various attributes of the mesh and putting up a weight for each attribute is often very difficult. This process frequently leads to visual distortion of the mesh. In some cases, if the data chosen for removal is actually important, fundamental characteristics or external appearance may be changed or else the degree of simplification is quite limited. Hence, the method of picking up not-so-relevant data for deletion is a critical issue.
In general, the edge collapsing method shown in FIG. 1 is suitable mostly for geometric treatment with due consideration to the cost resulting from positional change. Other factors such as curvature change in neighboring triangles and color change are mostly ignored. As for the vertex decimation method shown in FIG. 2, the method is limited to applications on a curve surface. For a three-dimensional mesh, deletion of vertices will be very difficult. In addition, any sharp cornered section or important section must be heavily weighted. Hence, if there is no unified scheme for weighing the attributes of a particular mesh, the simplification process may lead to serious warping.
Since most mesh simplification techniques estimate the cost of removing part of the data by considering some of the attributes only, major visual effects, characteristics and external appearance of a mesh are only partially considered. Moreover, no definite rules can be found to measure the cost of the removed attributes. For example, length or distance between the desired-to-remove data positions can be used to estimate positional variation. Similarly, change in the desired-to-remove normal data can be used to measure curvature variation and difference between the desired-to-remove color data can be used to compute color variation. The three attributes need to be integrated and balanced so that a final cost for removing part of the data can be obtained. Due to the absence of definite rules or standards, attributes are often poorly integrated leading to the destruction of fundamental characteristics and the restriction of mesh simplification.
Accordingly, one object of the present invention is to provide a method of using a fuzzy inference system to simplify meshes in computer graphics. A fuzzy inference system is used to integrate all possible attributes, and then the cost of eliminating the desired-to-remove data is estimated. Thereafter, the attributes are integrated to obtain a balance so that a final cost for the desired-to-remove data is determined. The final cost serves as a criteria for simplifying the mesh. Hence, after the mesh is simplified, all the good characteristics and visual appearance are retained. The method is suitable for progressive meshing. The method can be applied to multiresolution modeling rendering such as virtual reality, multimedia, computer graphics, three-dimensional games and progressive transmission within a network.
To achieve these and other advantages and in accordance with the purpose of the invention, as embodied and broadly described herein, the invention provides a method of using a fuzzy inference system to simplify meshes. First, m attributes are selected for a particular mesh. Variation of each attribute mi is characterized by n1 fuzzy sets, where 1xe2x89xa6ixe2x89xa6m. According to a fuzzy inference rule, variation of m attributes and the corresponding ni fuzzy sets, n1.n2 . . . nm different combinations are formed. Using a first function, n1.n2 . . . nm weights is computed from the n1.n2 . . . nm different combinations. According to the fuzzy inference rule, variation of the m attributes is next computed using a second function to obtain n1.n2. . . nm output values. Finally, according to the n1.n2 . . . nm weights and the n1.n2 . . . nm output values estimated cost is obtained by computation using a third function. The estimated cost serves as a parameter for removing data when simplifying the mesh.
The TSK fuzzy inference system can be used as the fuzzy inference rule. The first function, with respect to the n1.n2 . . . nm different combinations, can be defined in such a way that the one having the smallest membership value among the fuzzy sets that correspond to the variation of the m attributes is selected to obtain the n1.n. . . nm weights. The second function, with respect to the n1.n. . . nm different combinations, can be defined in such a way that cost of data removal, in other words, visual effects on the simplified mesh is selected to be the power of the variation of the m attributes followed by multiplying with each other, hence obtaining the n1.n2 . . . nm output values. The third function can be defined as the computation of a weighed average.
The fuzzy-based inference mesh simplification method of this invention is not limited to using TSK fuzzy inference system. For example, common Mamdani fuzzy inference system, Tsukamotos fuzzy inference system and so on can also be used, as long as all attributes within a mesh is considered without any loss of generality.
It is to be understood that both the foregoing general description and the following detailed description are exemplary, and are intended to provide further explanation of the invention as claimed.